
#ifndef __BITS_VECTOR__
#define __BITS_VECTOR__

#include <map>
#include "stdint.h"

namespace dta
{
	struct abs_bit_range_t
	{
		size_t head;
		size_t tail;
		bool valid() { return head <= tail; };
		size_t bit_size() { return tail - head; };
	};

	template < class T>
	T _min( T _1, T _2 )
	{
		return _1 < _2 ? _1 : _2;
	}

	template < size_t U8_NUM>
	class flat_bitmap_t
	{
	protected:

		size_t		_offset;
		uint8_t		_data[U8_NUM];

	public:

		enum { ELMT_BITS	= 8 };
		enum { TOTAL_BITS	= U8_NUM * ELMT_BITS };

		flat_bitmap_t( size_t start ) : _offset(start)
		{
			clear();
		}

		flat_bitmap_t( ) : _offset(0)
		{
			clear();
		}

		void update_offset( size_t offset )
		{
			_offset = offset;
		}
		void get_offset()
		{
			return _offset;
		}

		void clear()
		{
			memset( _data, 0, sizeof(_data) );
		}

		uint8_t & byte_ref( size_t bitoff )
		{
			return _data[bitoff>>3];
		}

		uint8_t * byte_ptr( size_t bitoff )
		{
			return _data + (bitoff>>3);
		}

		void set_bits( abs_bit_range_t & range, bool state )
		{
			if( !range.valid() ) return ;
			if( range.tail <= _offset ) return ;
			size_t head = max(range.head, _offset);
			size_t tail = min(range.tail, _offset + TOTAL_BITS );
			set_bits( head - _offset, tail - head, state );
			range.head = tail;
		}

		size_t test_bits( abs_bit_range_t & range )
		{
			if( !range.valid() ) return 0;
			if( range.tail <= _offset ) return 0;
			size_t head = max(range.head, _offset);
			size_t tail = min(range.tail, _offset + TOTAL_BITS );
			size_t r = test_bits( head - _offset, tail - head );
			range.head = tail;
			return r;
		}

		void set_bits( size_t bitoff, size_t num, bool state )
		{
			size_t u32index = bitoff / ELMT_BITS;
			size_t inu32off = bitoff % ELMT_BITS;
			for( ; num ; inu32off = 0, u32index ++ )
			{
				size_t to_set = min( ELMT_BITS - inu32off, num );
				num -= to_set;
				_set_bit_in_u8( u32index, inu32off, to_set, state );
			}
		}

		size_t test_bits( size_t bitoff, size_t num )
		{
			size_t u32index = bitoff / ELMT_BITS;
			size_t inu32off = bitoff % ELMT_BITS;
			for( ; num ; inu32off = 0, u32index ++ )
			{
				size_t to_set = min( ELMT_BITS - inu32off, num );
				num -= to_set;
				size_t m = _test_bit_in_u8( u32index, inu32off, to_set );
				if( m ) return m;
			}
			return 0;
		}

	protected:

		void _set_bit_in_u8( size_t index, size_t off, size_t bits, bool state )
		{
			uint8_t mask = -1;
			mask >>= (ELMT_BITS-bits); 
			mask <<= off;
			if( state ) _data[index] |= mask;
			else _data[index] &= ~mask;
		}

		size_t _test_bit_in_u8( size_t index, size_t off, size_t bits )
		{
			uint8_t mask = -1;
			mask >>= (ELMT_BITS-bits); 
			mask <<= off;
			return _data[index] & mask;
		}
	};

	struct wnd16_t
	{
		uint16_t *	_16ptr;
		uint8_t *	_8ptr_1;
		uint8_t *	_8ptr_2;

		operator uint16_t () const 
		{
			if( _16ptr ) return *_16ptr;
			return *_8ptr_1 << 8 | *_8ptr_2;
		}
		wnd16_t & operator = (uint16_t val ) 
		{
			if( _16ptr ) 
			{
				*_16ptr = val; 
				return *this;
			}
			*_8ptr_1 = ((val >> 8) & 0xff);
			*_8ptr_2 = (val & 0xff);
			return *this;
		}
		wnd16_t & operator |= ( uint16_t val ) 
		{
			if( _16ptr ) 
			{
				*_16ptr |= val; 
				return *this;
			}
			*_8ptr_1 |= ((val >> 8) & 0xff);
			*_8ptr_2 |= (val & 0xff);
			return *this;
		}
	};

	class bitmap_t
	{
	public:

		typedef flat_bitmap_t<0x200> page_bit_map_t;
		typedef std::map<size_t,page_bit_map_t>	space_bitmap_t;
		enum { CHUNK_BITS = page_bit_map_t::TOTAL_BITS };

	protected:

		space_bitmap_t	_space_map;

	public:

		bitmap_t()
		{
			
		}

		void set_bits( size_t bitoff, size_t num, bool state )
		{
			size_t index = bitoff / CHUNK_BITS;
			size_t offset = bitoff % CHUNK_BITS;
			for( ; num ; offset = 0, index ++ )
			{
				size_t to_set = _min( CHUNK_BITS - offset, num );
				num -= to_set;
				_set_bit_in_chunk( index, offset, to_set, state );
			}
		}

		size_t test_bits( size_t bitoff, size_t num )
		{
			size_t index = bitoff / CHUNK_BITS;
			size_t offset = bitoff % CHUNK_BITS;
			for( ; num ; offset = 0, index ++ )
			{
				size_t to_set = _min( CHUNK_BITS - offset, num );
				num -= to_set;
				size_t m = _test_bit_in_chunk( index, offset, to_set );
				if( m ) return m;
			}
			return 0;
		}

		uint8_t & operator [] ( size_t byteoff )
		{
			size_t bitoff = byteoff << 3;
			size_t index = bitoff / CHUNK_BITS;
			size_t offset = bitoff % CHUNK_BITS;
			page_bit_map_t & pgm = ref_page( index );
			return pgm.byte_ref(offset);
		}

		wnd16_t operator + ( size_t byteoff )
		{
			wnd16_t tmp = {};
			size_t bitoff = byteoff << 3;
			size_t index = bitoff / CHUNK_BITS;
			size_t offset = bitoff % CHUNK_BITS;
			if( offset + 16 > CHUNK_BITS )
			{
				// cross page
				page_bit_map_t & pgm1 = ref_page( index );
				tmp._8ptr_1 = pgm1.byte_ptr( offset );
				page_bit_map_t & pgm2 = ref_page( index + 1 );
				tmp._8ptr_2 = pgm2.byte_ptr( 0 );
			}
			else
			{
				page_bit_map_t & pgm = ref_page( index );
				tmp._16ptr = (uint16_t*)pgm.byte_ptr( offset );
			}
			return tmp;
		}

		void clear()
		{
			_space_map.clear();
		}

	protected:

		page_bit_map_t & ref_page( size_t index )
		{
			space_bitmap_t::iterator it = _space_map.find( index );
			if( it != _space_map.end() ) 
				return it->second;
			size_t offset = index * CHUNK_BITS;
			space_bitmap_t::value_type val(index,page_bit_map_t());
			val.second.update_offset(offset);
			space_bitmap_t::_Pairib ib = _space_map.insert(val);
			return ib.first->second;
		}
		page_bit_map_t * get_page( size_t index )
		{
			space_bitmap_t::iterator it = _space_map.find( index );
			if( it == _space_map.end() ) 
				return NULL;
			return &(it->second);
		}

		void _set_bit_in_chunk( size_t index, size_t off, size_t bits, bool state )
		{
			page_bit_map_t & pgm = ref_page( index );
			pgm.set_bits(off, bits, state );
		}

		size_t _test_bit_in_chunk( size_t index, size_t off, size_t bits )
		{
			page_bit_map_t * pgm = get_page( index );
			if( !pgm ) return 0;
			return pgm->test_bits(off, bits);
		}
	};
};


#endif
